package com.jz;

import com.future.util.TreeNode;

import java.util.LinkedList;

/**
 * Description: JZ84 二叉树中和为某一值的路径(三)
 *
 * @author weiruibai.vendor
 * Date: 2022/9/22 10:31
 */
public class JZ84 {

    // {1,0,1,1,2,0,-1,0,1,-1,0,-1,0,1,0},2
    // {2},2
    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        TreeNode A = new TreeNode(0);
        TreeNode B = new TreeNode(1);
        head.left = A;
        head.right = B;
        TreeNode AA = new TreeNode(1);
        TreeNode BB = new TreeNode(2);
        TreeNode CC = new TreeNode(0);
        TreeNode DD = new TreeNode(-1);
        A.left = AA;
        A.right = BB;
        B.left = CC;
        B.right = DD;
        AA.left = new TreeNode(0);
        AA.right = new TreeNode(1);
        BB.left = new TreeNode(-1);
        BB.right = new TreeNode(0);
        CC.left = new TreeNode(-1);
        CC.right = new TreeNode(0);
        DD.left = new TreeNode(1);
        DD.right = new TreeNode(0);

        JZ84 jz84 = new JZ84();

        int sum = 2;

        head = new TreeNode(2);

        int i = jz84.FindPath(head, sum);
        System.out.println(i);

    }

    public int FindPath(TreeNode root, int sum) {
        // write code here
        if (root == null) {
            return 0;
        }
        int ans = 0;
        LinkedList<TreeNode> link = new LinkedList<>();
        process(root, link);
        int rest;
        while (!link.isEmpty()) {
            rest = sum;
            TreeNode node = link.poll();
            ans += calc(node, rest);
        }
        return ans;
    }

    private int calc(TreeNode node, int rest) {

        if (node == null) {
            return 0;
        }
        rest = rest - node.val;
        int ans = 0;
        if (rest == 0) {// ！！！！
            ans = 1;
        }
        ans += calc(node.left, rest);
        ans += calc(node.right, rest);
        return ans;
    }

    private void process(TreeNode root, LinkedList<TreeNode> link) {
        if (root == null) {
            return;
        }
        link.add(root);
        // 左
        process(root.left, link);
        // 右
        process(root.right, link);
    }
}
